#pragma once

#include <vector>

namespace solution_590
{

class Node
{
public:
    int val;
    std::vector<Node*> children;
    Node() { }
    Node(int _val) : val(_val) { }
    Node(int _val, std::vector<Node*> _children) : val(_val), children(_children) {}
};

class Solution
{
public:
    std::vector<int> postorder(Node* root)
    {
        std::vector<int> visited;
        traverse_postorder(root, visited);
        return visited;
    }

    std::vector<int> postorder2(Node* root)
    {
        std::vector<int> visited;
        std::vector< std::pair<Node*, int> > stack;

        Node* last_visited = nullptr;
        while (!stack.empty() || root) {
            if (root) {
                stack.emplace_back(root, 0);
                root = root->children.empty() ? nullptr : root->children.front();
            } else {
                auto& tail = stack.back();
                if (tail.first->children.empty() || tail.first->children.back() == last_visited) {
                    visited.push_back(tail.first->val);
                    last_visited = tail.first;
                    stack.pop_back();
                } else {
                    root = tail.first->children.at(++tail.second);
                }
            }
        }

        return visited;
    }

private:
    void traverse_postorder(Node* root, std::vector<int>& visited)
    {
        if (!root)
            return;
        for (auto node : root->children)
            traverse_postorder(node, visited);
        visited.push_back(root->val);
    }
};

}  /* namespace 590 */
